home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 050 / xrf.arc / XRF2.C < prev    next >
Encoding:
C/C++ Source or Header  |  1986-04-20  |  6.3 KB  |  174 lines
  1. /*
  2.  *                      ***************
  3.  *                      * X R F 2 . C *
  4.  *                      ***************
  5.  *
  6.  * This file contains the identifier tree and reference list management
  7.  * things. It uses a simple binary tree to store the identifiers for
  8.  * lookup and later sorted printing. Each node in the id tree has a
  9.  * pointer to the id string, left and right links and pointers to the
  10.  * beginning and end of the linked list of reference nodes for that
  11.  * id. Only the root of the tree is global, it is used by the sorted
  12.  * index printing function 'prtree'.
  13.  *
  14.  * Version V1.3          9-May-80
  15.  * Version V1.4        10-Jul-80 MM    Bummed coe
  16.  * Version V1.5        23-Jul-80 MM    Redid storage code
  17.  * Version V1.6        23-Dec-80 RBD    Fixed bug in myalloc()
  18.  * Version V1.7         8-Jan-85 MC    Document key change for non 
  19.  *                    case-sensitive keys/concatanation.
  20.  * Version V1.17    29-Mar-85 MC    write tree to disk if no core 
  21.  */
  22.  
  23. #include <stdio.h>
  24. #include "xrf.h"
  25.  
  26. /*
  27.  * Tree search and insertion. This function returns a pointer to
  28.  * the new node if created. This may require some head scratching
  29.  * (I had to!). Look particularly at the significance of the pointer
  30.  * that is returned and how it is used by the recursive caller. If
  31.  * you want more, read "Algorithms + Data Structures = Programs"
  32.  * by Niklaus Wirth (Prentice Hall ISBN 0-13-022418-9) Chapter 4.
  33.  *
  34.  * It searches through the tree for a match to the supplied id (*kp).
  35.  * If it is found, a new reference node is linked into the list for
  36.  * that id. If no match is found, a new is node is inserted into the
  37.  * tree and appropriately initialized, including a first reference
  38.  * node.
  39.  *
  40.  * The node is now positioned in the tree in case non-sensitive order.
  41.  * This means that in the final list mixed, upper & lower case symbols
  42.  * appear togethor instead of being separated in the collating sequence.
  43.  * Also the source name is present for file concatanation.
  44.  *
  45.  * The id (*kp) now comes as <KEYactualNNNNNNNN> from XRF0.C where:-
  46.  *                      KEY                is the symbol as lower case
  47.  *                                                  length CPS characters.
  48.  *                               actual          is the symbol as she appears
  49.  *                                                  length CPS characters.
  50.  *                           NNNNNNNN  is the program name
  51.  *                                                  length 8 chars
  52.  *
  53.  */
  54.  
  55. static int memfull =0;
  56.  
  57. struct idt *search(kp, link)            /* Function "search" */
  58. struct idt *link;                       /* Pointer to id node in tree */
  59. char *kp;                               /* Pointer to key string */
  60. { struct id *n,*placenode();
  61.     memfull =0;
  62.     n=placenode(kp, link);        /* insert new ref */
  63.     if(memfull)return NULL;        /* if can't, flag NO CORE */
  64.     return n;                /* else return new root */
  65. }
  66. static struct idt *placenode(kp, link)    /* Function "placenode" */
  67. struct idt *link;                       /* Pointer to id node in tree */
  68. char *kp;                               /* Pointer to key string */
  69. { struct idt *l;                        /* Fast tree pointer */
  70.   struct ref *r;                        /* Fast list pointer */
  71.   struct ref *newref();            /* Make reference function */
  72.   int cond;                             /* Condition from strcmp */
  73.   char *malloc();
  74.     l = link;                           /* Copy link into register */
  75.     if(l == NULL){                      /* Not found, insert new id node */
  76.         if((l=(struct idt *)malloc(sizeof(struct idt)))==NULL){
  77.         memfull++;
  78.         return NULL;
  79.         }                /* Get string space if can*/
  80.     if((l->keyp = malloc(strlen(kp)+1))==NULL){
  81.         free(l);
  82.         memfull++;
  83.         return NULL;
  84.         }
  85.                                         /* Fill in pointer to ... */
  86.         strcpy(l->keyp, kp);              /* ... stashed key string */
  87.         l->left = l->right = NULL;        /* No children */
  88.         if((r = newref())==NULL){         /* Attach it to the id node */
  89.         free(l->keyp);
  90.         free(l);
  91.         memfull++;
  92.         return NULL;
  93.         }
  94.         l->last = l->first = r;
  95.         namcnt++;
  96.         refcnt++;
  97.         }
  98.     else if((cond = strcmp(kp, l->keyp)) == 0){ /* Match if true */
  99.       if((r = newref())==NULL){     /* Get a new ref. node */
  100.     memfull++;
  101.     return(l);        /* can't */
  102.     }
  103.       l->last->next = r;         /* Hook new node into the list */
  104.       l->last = r;
  105.       refcnt++;
  106.       }
  107.     else if(cond < 0)                    /* Look left */
  108.       l->left = placenode(kp, l->left);
  109.     else                                 /* Look right */
  110.       l->right = placenode(kp, l->right);
  111.     return(l);
  112. }
  113.  
  114.  
  115. /*
  116.  * Initialize a line number referece
  117.  */
  118.  
  119. static struct ref*
  120. newref()
  121. { char *malloc();
  122.   struct ref *r;
  123.    if((r = (struct ref *)malloc(sizeof(struct ref)))==NULL)
  124.     return NULL;            /* Make a reference node */
  125.    r->lno = lineno;                     /* Fill in line no. of ref. */
  126.    r->next = NULL;                      /* This is the end for now */
  127.    return(r);                /* Return pointer to the node */
  128. }
  129.  
  130. /*--------------------------------------------*/
  131. /*  return all storage to system              */
  132. /*--------------------------------------------*/
  133. myfree(base)        /*WARNING will not update 'base' pointer */
  134. struct idt *base;
  135. { struct idt *delidt();
  136.     delidt(base);
  137. }
  138.  
  139. struct idt *delidt(link)
  140. struct idt *link;
  141. { struct idt *next;
  142.    if (link != NULL){
  143.       link->left=delidt(link->left);           /* Visit the left */
  144.       link->right=delidt(link->right);         /* Visit the right */
  145.       if(link->left==NULL&&link->right==NULL){ /* no children, so ... */
  146.         delrefs(link->first);                  /* .. remove refs */
  147.         free(link->keyp);                      /* .. kill key store */
  148.         free(link);                            /* .. return space */
  149.         return NULL;                           /* .. update parent */
  150.         }
  151.      }
  152.    return NULL;                                /* this went nowhere */
  153.  
  154. }
  155. delrefs(link)
  156. struct ref *link;
  157. { struct ref *p;
  158.     while(link!=NULL){
  159.          p=link;
  160.          link=link->next;
  161.          free(p);
  162.          }
  163. }
  164.  
  165. /*
  166.  * 'quit' handles dynamic memory deficit. (Sounds like U.S. Government!).
  167.  * It issues a polite message to the user, marks the list file for delete
  168.  * and exits to RSX.
  169.  *
  170.  */
  171.  
  172. quit()
  173. { abort("Not enough memory space, sorry.\n"); }
  174.